"""
1. 首先，初始化res作为返回结果，初始化path作为路径
2. 然后，回溯函数
    如果当前start已经走到字符串末尾
        添加到res中
        返回
    
    遍历(start, n)
        如果start, i组成的字符串不是回文串，则直接跳过
        
        将回文串加入path
        递归本身(path, s, i + 1),i+1表示跳过当前字符
        pop后退一步

3. 回文函数
    如果左指针< 右指针
        如果两者不相等，直接返回
        否则更新左右指针
    遍历结束返回TRUE

4. 调用回溯函数并返回res
"""

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if not s:
            return []
        
        res = []
        path = []
        n = len(s)
        
        def back_track(path, start, n):
            if n == start:
                res.append(path[:])
                return
            
            for i in range(start, n):
                if not palind(start, i):
                    # s[start: i+1]
                    continue

                path.append(s[start: i + 1])    # 添加s[start, i + 1]
                back_track(path, i + 1, n)
                path.pop()
        
        def palind(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False

                l += 1
                r -= 1
            return True

        back_track(path, 0, n)
        return res
    